package 比特教务管理系统.双链表;

public class MyDoubleLinkedList {
    static class Node{
        public int data;
        public Node prev;
        public Node next;
        public Node(int val){
//            super();
            this.data = val;
        }

        public void displayNode(){
            System.out.print("("+data+")");
        }
    }

    private Node head;

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }

    public Node getLast() {
        return last;
    }

    public void setLast(Node last) {
        this.last = last;
    }

    private Node last;

//    public MyDoubleLinkedList(){
//        head = null;
//        last = head;
//    }

    public boolean isEmpty(){
        return head == null;
    }

    /**
     * 头插法
     * @param data 插入的结点数据
     */
    public void insertFirst(int data){
        Node newNode = new Node(data);
        if (isEmpty()){
            //如果链表为空,那么直接让最后的结点先指向这个新结点
            last = newNode;
        }else {
            //如果链表不为空,那么就要对head结点进行修改
            head.prev = newNode;
            //先让头元素的prev指针指向newNode
        }
        //然后再让新结点的next指针指向原来的头元素
        newNode.next = head;
        //最后改变头节点引用head的指向
        head = newNode;
    }

    /**
     * 尾插法
     * @param data 插入元素的值
     */
    public void insertLast(int data){
        Node newNode = new Node(data);
        if (isEmpty()){
            //如果链表为空,则对head和last进行修改,
            //因为修改last的操作不管链表是否为空都要做,所以放在if-else循环外面
            head = newNode;
        }else {
            newNode.prev = last;
            last.next = newNode;
        }
        last = newNode;
    }

    /**
     * 指定索引位置元素后插入
     * 插入成功返回true,插入失败返回false
     * @param index 索引
     * @param data 插入元素值
     */
    public boolean insertIndex(int index, int data){
        Node current = head;
        Node newNode = new Node(data);
        if (isEmpty()){
            //如果链表为空,则插入的元素一律定为头元素
//            head = newNode;
//            last = head;
            //我们这里直接返回false
//            System.out.println("链表为空,已将该结点添加至链表首位");
            return false;
        } else {
            //如果链表不为空,我们先找到索引对应的位置
            for (int i=0;i<index;i++){
                current = current.next;
                if (current == null) return false;
            }
            //然后对current和后面的一个结点进行插入工作的修改

            newNode.next = current.next;
            newNode.prev = current;
            current.next.prev = newNode;
            current.next = newNode;
            //这里顺序一定不能搞错,先在newNode上进行修改
            //否则先修改current的话会丢失原本current的下一个结点
            return true;
        }
    }

    /**
     * 删除尾巴结点
     * @return 删除成功返回true,失败返回false
     */
    public boolean deleteLast(){
        if (isEmpty()){
            return false;
        }else if (head == last){
            head = null;
            last = null;
            return true;
        }else {
            last = last.prev;
            last.next.prev = null;
            last.next = null;
            return true;
        }
    }

    /**
     * 头删法
     * @return 删除成功返回true,失败返回false
     */
    public boolean deleteFirst(){
        if (isEmpty()){
            System.out.println("链表为空,无法删除");
            return false;
        }else if (head == last){
            head = null;
            last = null;
            return true;
        }else {
//            last = last.prev;
//            last.next.prev = null;
//            last.next = null;
//            return true;
            head = head.next;
            head.prev.next = null;
            head.prev = null;
            return true;
        }
    }

    /**
     * 删除对应索引位置的结点
     * @param index 删除结点的索引
     * @return 删除成功返回true,失败返回false
     */
    public boolean deleteIndex(int index){
        if (isEmpty()){
            System.out.println("链表为空,无法删除");
            return false;
        }else {
            Node current = head;
            for (int i=0;i<index;i++){
                current = current.next;
                if (current == null) {
                    System.out.println("索引处无元素");
                    return false;
                }
            }
            current.prev.next = current.next;
            current.next.prev = current.prev;
            current.prev = null;
            current.next = null;
            return true;
        }
    }

    /**
     * 删除对应值的首个结点
     * @param key 删除结点的值
     * @return 删除成功返回true,失败返回false
     */
    public boolean deleteFirstKey(int key){
        Node current = head;
        if (isEmpty()){
            return false;
        }else {
            while (current.next != null){
                if (current.data == key){
                    if (current == head){
                        current.next.prev = null;
                        head = current.next;
                        current.next = null;
                        return true;
                    }
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                    current.next = null;
                    current.prev = null;
                    return true;
                }else {
                    current = current.next;
                }
            }
            //程序运行到这里说明到达了最后一个结点
            if (current.data == key){
                current.prev.next = null;
                current.prev = null;
                return true;
            }else {
                System.out.println("没有相关元素");
                return false;
            }
        }
    }

    /**
     * 删除对应值的所有结点
     * @param key 删除节点的值
     * @return 删除成功返回true,失败返回false
     */
    public boolean deleteAllKey(int key){
        Node current = head;
        if (isEmpty()){
            return false;
        }else {
            while (current.next != null){
                if (current.data == key){
                    if (current == head){
                        head = current.next;
                        current = current.next;
                        current.prev.next = null;
                        current.prev = null;
                        continue;
                    }
                    current = current.next;
                    current.prev.prev.next = current;
                    current.prev = current.prev.prev;
//                    current.prev.prev = null;
//                    current.prev.next = null;
                }else {
                    current = current.next;
                }
            }
            //程序运行到这里说明到达了最后一个结点
            if (current.data == key){
                current.prev.next = null;
                current.prev = null;
                return true;
            }else {
                return false;
            }
        }
    }

    /**
     * 从头到尾展示链表
     */
    public void displayAll(){
        System.out.print("List:");
        Node current = head;
        while(current!=null){
            current.displayNode();
            current = current.next;
        }
        System.out.println();
    }

}
